YaoのGarbled Circuitについて
TL;DR
YaoのGarbled Circuitは、参加者間で互いの情報を明かさずに、ある計算を行うプロトコル
具体例をベースにプロトコルの流れを紹介
はじめに
今回は論文本文の内容ではなく、Garblet Circuitのプロトコルについて紹介する。
本文
二人のミリオネアが自分の資産を開示することなく、どちらがよりお金持ちかを知りたいという問題を考える。より定式的には、x1, x2を明かさずに以下の問題を解きたいというものだ。
x1 < x2 の場合、 f(x1, x2) = 1
それ以外の場合、f(x1, x2) = 0
これをナイーブに実装するなら、信頼できる第三者を用意し、比較結果した結果を返せばよい。ただし、この実装では、この第三者には資産(x1, x2)が漏洩してしまう。
ミリオネアの問題を解く(元論文第3.1節より)
Aliceが $ imillions 、Bobが $ jmillionsの所持金
ここで $ 1 < i, j < 10
各々の所持金についての情報と、最終結果($ i < jかどうか)だけを知ることができる
$ M: $ N-bit非負整数の集合
$ Q_N: $ M \to Mの1:1写像
$ E_a: $ Q_Nの乱数から生成したAliceの公開鍵暗号
プロトコル
Bobはランダムに$ N-bitの整数を選び、結果$ k = E_a(x)を計算
BobはAliceに$ k-j+1を送信
Aliceは$ y_u = D_a(k-j+u)を計算
$ u = 1,2,...,10
cipepser.icon $ D_a が定義されていないが、復号と思われる
cipepser.icon $ k-j+1〜$ k-j+9($ 1 \leq j \leq 9)を計算している。どれか一つだけ$ jがキャンセルするので、$ y_u = D_a(k) = D_a(E_a(x)) = xとなる。ただし、Aliceは9個のうち、どれが$ xと一致したのかはわからない
Aliceはランダムな$ N/2bit素数$ pを生成し、すべての$ uについて、$ z_u = y_u \ mod \ pを計算
素数の生成は、すべての$ z_uが2つ以上異なるまで繰り返す
Aliceは素数$ pと、$ z_1, z_2, ..., z_iと続く$ z_i + 1, z_{i+1} + 1, ..., z_{10}+1を送る(mod pして送る)
BobはAliceから受け取った数字の内、$ j番目の数字を確認し、$ xと一致するか確認することで、$ i \geq jを決定する
cipepser.icon $ z_1, z_2, ..., z_iで$ xと一致した場合は、$ j \leq iといえる。逆に(+1されたせいで)一致するものがなかった場合は、$ i < jになる
BobはAliceに結果を伝える
以上のように互いの情報を明かさずに、どちらの資産が多いかを判別することが可能となる。さらにYao氏の論文ではm人に一般化しているとともに、秘密投票などでも使えること、ε-δプライバシーについても触れられている。ページ数も5ページ程度のため、興味がある方はぜひ読んでみてほしい。(文責・恩田) 参考
Yao, Andrew C. "Protocols for secure computations." 23rd annual symposium on foundations of computer science (sfcs 1982). IEEE, 1982.
菊池亮. "安全なデータ活用を実現する秘密計算技術: 4. Garbled circuit を用いた秘密計算と混合的構成." 情報処理 59.10 (2018): 893-897.